import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Text5 {
    //18.四数之和
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);

        int n = nums.length;
        for (int i = 0;i < n ; ){
            for (int j = i + 1;j < n ; ){
                int left = j + 1,right = n - 1;
                //易错1
                long sum1 = (long)target - nums[i] - nums[j];
                while(left < right){
                    int sum2 = nums[left] + nums[right];
                    if (sum2 < sum1){
                        left++;
                    } else if (sum2 > sum1){
                        right--;
                    } else {
                        ret.add(new ArrayList<Integer>(Arrays.asList(nums[left++],nums[right--],nums[i],nums[j])));
                        while(left < right && nums[left] == nums[left-1]) left++;
                        while(left < right && nums[right] == nums[right+1]) right--;
                    }
                }
                j++;
                while(j < n  && nums[j] == nums[j-1]) j++;
            }
            //易错2
            i++;
            while(i < n  && nums[i] == nums[i-1]) i++;
        }

        return ret;
    }
}
